package main

import (
	"fmt"
	"strconv"
	"sync"
	"time"
)

func main() {
	//zhizhen()

	//weiyunsuan()

	//xiecheng()
	//通道之间传输数据
	zhizhen()
	//调用二分查找-----------------
	arr := []int{9, 11, 13, 1, 3, 5, 7}
	//调用冒泡排序-----------------
	fmt.Println("排序前：", arr)
	// 调用冒泡排序（直接修改原数组）
	bubbleSort(arr)
	// 输出排序结果
	fmt.Println("排序后：", arr)
	//调用二分查找-----------------
	target := 7
	// 调用二分查找
	index := binarySearch(arr, target)
	// 输出结果
	if index != -1 {
		fmt.Printf("目标值 %d 在数组中的索引为：%d\n", target, index)
	} else {
		fmt.Printf("目标值 %d 未在数组中找到\n", target)
	}
}

// 冒泡排序
func bubbleSort(arr []int) {
	n := len(arr)
	if n <= 1 {
		return // 数组长度为 0 或 1 时，已有序，无需排序
	}

	// 外层循环：控制排序轮数（最多需要 n-1 轮，因为每轮会确定一个最大元素的位置）
	for i := 0; i < n-1; i++ {
		// 标记：本轮是否发生过交换（初始为 false）
		swapped := false

		// 内层循环：每轮比较的次数（第 i 轮后，末尾 i 个元素已有序，无需再比较）
		// 例如：第 1 轮比较 n-1 次，第 2 轮比较 n-2 次，...，第 i 轮比较 n-1-i 次
		for j := 0; j < n-1-i; j++ {
			// 相邻元素比较：如果前一个元素 > 后一个元素，交换两者（保证升序）
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j] // Go 中直接交换两个变量，无需临时变量
				swapped = true                      // 标记本轮发生了交换
			}
		}

		// 优化：如果本轮没有交换，说明数组已完全有序，提前退出循环（无需继续后续轮次）
		if !swapped {
			break
		}
	}
}

// 二分查找
func binarySearch(arr []int, target int) int {
	// 初始化左右指针：left 指向数组开头，right 指向数组末尾
	left, right := 0, len(arr)-1

	// 循环条件：left <= right（当 left > right 时，说明区间内无目标值，查找结束）
	for left <= right {
		// 计算中间索引：避免直接 (left+right) 可能导致的整数溢出（Go 中 int 是 64 位，但养成好习惯）
		mid := left + (right-left)/2

		// 1. 中间值等于目标值：找到目标，直接返回索引
		if arr[mid] == target {
			return mid
		}

		// 2. 中间值小于目标值：目标值可能在 mid 右侧（因为数组升序），所以移动 left 到 mid+1
		if arr[mid] < target {
			left = mid + 1 // 排除 mid 左侧的区间（左侧值都比目标小）
		} else {
			// 3. 中间值大于目标值：目标值可能在 mid 左侧，移动 right 到 mid-1
			right = mid - 1 // 排除 mid 右侧的区间（右侧值都比目标大）
		}
	}

	// 循环结束后仍未找到：说明目标值不在数组中，返回 -1
	return -1
}

// 多维指针（可以更多维）
func zhizhen() {
	num := 10
	ptr := &num
	ptr2 := &ptr
	// 三维指针，指向二维指针 ptr2
	var ptr3 ***int = &ptr2
	fmt.Printf("num  的值: %d\n", num)
	fmt.Printf("ptr  指向的值: %d\n", *ptr)
	fmt.Printf("ptr2 间接指向的值: %d\n", **ptr2)
	fmt.Printf("ptr3 间接指向的值: %d\n", ***ptr3)
	// 通过三维指针修改 num 的值
	***ptr3 = 40
	fmt.Printf("修改后 num 的值: %d\n", num)
}

// 位运算符
func weiyunsuan() {
	a := 5              // 二进制表示为 0101
	result := a << 2    // 左移 2 位（相当于a*(2*2*2)）
	fmt.Println(result) // 输出 20，二进制为 10100

	b := 5              // 二进制表示为 0101
	result = b >> 2     // 右移 2 位（相当于5/(2*2)） 等于1.25然后向下取整
	fmt.Println(result) //输出1

	num := 7
	result = num >> 1
	fmt.Println(result) //输出3
}

// 使用协程主函数
func xiecheng() {
	//声明一个协程执行外部函数
	go func() {
		for i := 1; i <= 5; i++ {
			time.Sleep(200 * time.Millisecond)
			fmt.Println(i)
		}
	}()
	// 主协程继续执行其他任务
	for j := 'a'; j <= 'e'; j++ {
		time.Sleep(300 * time.Millisecond)
		fmt.Printf("%c\n", j)
	}
	//上面这两个同时在控制台打印 没有先后  就看谁先打印完
	//如果没有这个睡眠函数控制台什么都不会打印
	time.Sleep(2 * time.Second)
}

// 使用通道在协程之间同行
func chanData() {
	ch1 := make(chan string)
	ch2 := make(chan int)
	//辛克
	var wg sync.WaitGroup
	//创建数据
	wg.Add(1) //等待对象加一
	go func() {
		defer wg.Done()
		for j := 'a'; j <= 'h'; j++ {
			ch1 <- string(j)
		}
	}()
	//创建数据
	wg.Add(1) //等待对象加一
	go func() {
		defer wg.Done()
		for i := 1; i <= 5; i++ {
			ch2 <- i
		}
	}()
	//消费数据
	wg.Add(1) //等待对象加一
	go func() {
		defer wg.Done()
		ticker := time.NewTicker(3 * time.Second)
		defer ticker.Stop()
		for {
			allClosed := true
			select {
			case str := <-ch1:
				fmt.Println("\n", str)
				allClosed = false
			case str := <-ch2:
				allClosed = false
				fmt.Println("\n", strconv.Itoa(str))
			case <-ticker.C:
				fmt.Println("已超时")
			}
			if allClosed {
				return
			}
		}
	}()
	wg.Wait()
}

// 1.18之后引入的泛型
func Max[T int | float64](a, b T) T {
	if a > b {
		return a
	}
	return b
}

// 深度优先搜索------------------------------------------------------------------------------------------------------------------------
// 调用深度优先搜索
func testShendu() {
	// 示例：图的邻接表表示（无向图）
	// 节点 1 连接 2、3；节点 2 连接 1、4、5；节点 3 连接 1；节点 4 连接 2；节点 5 连接 2
	graph := map[int][]int{
		1: {2, 3},
		2: {1, 4, 5},
		3: {1},
		4: {2},
		5: {2},
	}
	fmt.Println("递归版 DFS 遍历结果：")
	visited := make(map[int]bool)   // 初始化 visited 集合
	dfsRecursive(graph, 1, visited) // 从节点 1 开始遍历
	fmt.Println("\n栈版 DFS 遍历结果：")
	dfsStack(graph, 1) // 从节点 1 开始遍历
}

// 1. 递归实现：适用于树、图等结构，代码简洁
// dfsRecursive 深度优先搜索（递归版）：从图的起始节点出发，遍历所有可达节点
// 核心逻辑：“一路走到底，走不通再回溯”，用递归栈实现回溯
// 参数：
//
//	graph: 图的邻接表表示（key：节点，value：与该节点相连的邻居节点列表）
//	start: 起始节点
//	visited: 记录已访问的节点（避免重复访问，防止环导致死循环）
func dfsRecursive(graph map[int][]int, start int, visited map[int]bool) {
	// 1. 标记当前节点为已访问
	visited[start] = true
	// 2. 处理当前节点（这里简单打印节点值）
	fmt.Printf("%d ", start)

	// 3. 递归遍历当前节点的所有未访问邻居
	for _, neighbor := range graph[start] {
		if !visited[neighbor] { // 只有未访问过的邻居才递归
			dfsRecursive(graph, neighbor, visited)
		}
	}
}

// 2. 栈实现：适用于避免递归深度过大导致的栈溢出，逻辑更直观
// dfsStack 深度优先搜索（栈版）：用栈模拟递归过程，手动控制回溯
// 参数和返回值同递归版
func dfsStack(graph map[int][]int, start int) {
	// 初始化栈（存储待访问的节点），将起始节点入栈
	stack := []int{start}
	// 初始化 visited 集合，记录已访问的节点
	visited := make(map[int]bool)

	// 循环：栈不为空时，继续访问
	for len(stack) > 0 {
		// 1. 弹出栈顶节点（当前要访问的节点）
		current := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		// 2. 如果当前节点未访问过：处理它，并将其邻居入栈
		if !visited[current] {
			visited[current] = true    // 标记为已访问
			fmt.Printf("%d ", current) // 处理当前节点

			// 3. 将当前节点的所有未访问邻居入栈（注意：栈是后进先出，所以逆序入栈，保证遍历顺序和递归版一致）
			// 例如：邻居 [2,3]，逆序后 [3,2]，入栈后弹出顺序是 2、3，和递归版一致
			for i := len(graph[current]) - 1; i >= 0; i-- {
				neighbor := graph[current][i]
				if !visited[neighbor] {
					stack = append(stack, neighbor)
				}
			}
		}
	}
}

// 广度优先搜索------------------------------------------------------------------------------------------------------------------------
// 调用广度优先搜索
func testGuangdu() {
	// 示例：图的邻接表表示（无向图）
	// 节点 1 连接 2、3；节点 2 连接 1、4、5；节点 3 连接 1；节点 4 连接 2；节点 5 连接 2
	graph := map[int][]int{
		1: {2, 3},
		2: {1, 4, 5},
		3: {1},
		4: {2},
		5: {2},
	}

	fmt.Println("BFS 遍历结果：")
	bfs(graph, 1) // 从节点 1 开始遍历
}

// bfs 广度优先搜索：从图的起始节点出发，按“层次”遍历所有可达节点
// 核心逻辑：“先访问当前节点的所有邻居，再访问邻居的邻居”，用队列实现层次管理（时间复杂度 O(n)，n 为节点数）
// 典型应用：最短路径（无权图）、层序遍历（树）、寻找所有可达节点
// 参数：
//
//	graph: 图的邻接表表示（key：节点，value：与该节点相连的邻居节点列表）
//	start: 起始节点
func bfs(graph map[int][]int, start int) {
	// 1. 初始化队列（存储待访问的节点），将起始节点入队
	queue := []int{start}
	// 2. 初始化 visited 集合，记录已访问的节点（避免重复访问，防止环导致死循环）
	visited := make(map[int]bool)
	// 3. 标记起始节点为已访问（入队时标记，避免重复入队）
	visited[start] = true

	// 循环：队列不为空时，继续访问
	for len(queue) > 0 {
		// 4. 出队队首节点（当前要访问的节点）
		current := queue[0]
		queue = queue[1:] // 移除队首元素

		// 5. 处理当前节点（这里简单打印节点值）
		fmt.Printf("%d ", current)

		// 6. 将当前节点的所有未访问邻居入队（按顺序入队，保证层次遍历）
		for _, neighbor := range graph[current] {
			if !visited[neighbor] { // 只有未访问过的邻居才入队
				visited[neighbor] = true        // 入队时标记为已访问，避免重复入队
				queue = append(queue, neighbor) // 入队
			}
		}
	}
}
